#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

//给定两个按照升序排列的有序数组，请把它们合成一个升序数组并输出
/*
 * input
 *	第一行为第一个有序数组的长度，正整数n， n <= 20
 *	第二行为第一个有序数组的n个数字，用空格隔开
 *	第三行为第二个有序数组的长度，正整数m，m <= 20
 *	第四行为第二个有序数组的m个数字，用空格隔开
 * output
	输出合并后的数组
举例：
输入
	3
	1 3 7
	5
	2 4 6 8 10
输出
	1 2 3 4 6 7 8 10

本程序
	merge：合并2个有序数组
	merge_list：合并两个有序链表
 * */

void print_ary(char* name, int* ary, int len)
{
	int i;
	printf("%s is: ", name);
	for (i = 0; i < len; i++)
		printf("%d ", ary[i]);
	printf("\n");
}

void merge(int *ary1, int ary1_len, int *ary2, int ary2_len)
{
	int *result = NULL;
	int len = ary1_len + ary2_len;
	int i, j, k, min_len;

	result = malloc(len * sizeof(int));
	memset(result, 0, len * sizeof(int));

	//main part start
	/*从头开始比较两个数列中的数，
	 * 哪一个小就取出依次存入新的数组中，
	 * 直到其中一个全部比较完，
	 * 将另一个数组剩下的部分直接存入新的数组中
	 */
	min_len = ary1_len;
	if (ary2_len < ary1_len)
		min_len = ary2_len;
	for(i = 0, j = 0, k = 0; (i < min_len) && (j < min_len);) {
		if (ary1[i] <= ary2[j]) {
			result[k] = ary1[i];
			i++;
		} else {
			result[k] = ary2[j];
			j++;
		}
		k++;
	}
	for (; i < ary1_len; i++, k++) {
		result[k] = ary1[i];
	}
	for (; j < ary2_len; j++, k++) {
		result[k] = ary2[j];
	}
	//main part end
	print_ary("ary1", ary1, ary1_len);
	print_ary("ary2", ary2, ary2_len);
	print_ary("merge result", result, len);
	printf("\n");

	free(result);
}

struct simplist {
	struct list_head list;
	int val; //header node saved the length
};

void build_list_by_ary(struct simplist* plist, int *ary, int len)
{
	int i;
	struct simplist* node;
	for (i = 0; i < len; i++) {
		node = malloc(sizeof(struct simplist));
		node->val = ary[i];
		INIT_LIST_HEAD(&node->list);
		list_add_tail(&node->list, &plist->list);
	}
	plist->val = len;
}

void destroy_list(struct simplist* plist)
{
	struct simplist* cur;
	struct simplist* n;
	list_for_each_entry_safe(cur, n, &plist->list, list, struct simplist) {
		list_del(&cur->list);
		free(cur);
	}
}

void print_list(char* name, struct simplist* plist)
{
	struct simplist* cur;
	printf("%s is: ", name);
	
	list_for_each_entry(cur, &plist->list, list, struct simplist) {
		printf("%d ", cur->val);
	}
	printf("\n");
}

//add 'cur' node to 'presult' list tail, and update result list length
//return cur->next node
//返回当前节点的下一个节点（合并前的链表中的下一个节点）
struct simplist* insert_node(struct simplist* cur, struct simplist* presult)
{
	struct simplist *next;
	next = list_next_entry(cur, struct simplist, list);
	list_add_tail(&cur->list, &presult->list);
	presult->val++; //update the list length
	return next;
}

void merge_list(struct simplist* plist1, struct simplist* plist2)
{
	struct simplist result, *presult;
	struct simplist *cur1, *cur2;

	INIT_LIST_HEAD(&result.list);
	presult = &result;
	presult->val = 0;

	print_list("list1", plist1);
	print_list("list2", plist2);
	//main part start
	/*从头开始比较两个数列中的数，
	 * 哪一个小就取出依次存入新的数组中，
	 * 直到其中一个全部比较完，
	 * 将另一个数组剩下的部分直接存入新的数组中
	 * 注意，这里直接把之前链表的节点放入新链表
	 * 所以之前的链表结构是乱的，不能打印
	 * 释放资源也只能释放合并后的链表的
	 * 因为合并后的链表包含之前2个链表的所有节点
	 */
	cur1 = list_next_entry(plist1, struct simplist, list);
	cur2 = list_next_entry(plist2, struct simplist, list);
	while (1) {
		if (list_entry_is_head(cur1, &plist1->list, list) || 
			list_entry_is_head(cur2, &plist2->list, list))
			break;
		if (cur1->val <= cur2->val)
			cur1 = insert_node(cur1, presult);
		else
			cur2 = insert_node(cur2, presult);
	}

	while (!list_entry_is_head(cur1, &plist1->list, list))
		cur1 = insert_node(cur1, presult);
	while (!list_entry_is_head(cur2, &plist2->list, list))
		cur2 = insert_node(cur2, presult);

	print_list("merge result", presult); 
	destroy_list(presult);
}

int main(int argc, char** argv)
{
	int ary1[] = {1, 3, 7};
	int ary1_len = 3;
	struct simplist list1, list2;

	int ary2[] = {2,4,6,8,10};
	int ary2_len = 5;
	merge(ary1, ary1_len, ary2, ary2_len);

	INIT_LIST_HEAD(&list1.list);
	INIT_LIST_HEAD(&list2.list);
	build_list_by_ary(&list1, ary1, ary1_len);
	build_list_by_ary(&list2, ary2, ary2_len);
	merge_list(&list1, &list2);

	return 0;
}

